home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / web / c_cpp / cnoweb / pf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-20  |  10.0 KB  |  372 lines
  1. /*
  2.       pf.c in c-no-web format.  (8/10/89)
  3.       by Jim Fox, University of Washington
  4.  
  5.  \input cnoweb   % load the c-no-web system
  6. %
  7. % \nweb ... \bewn = \cnoweb commentary
  8.   \def\nweb{\leavevmode\begingroup\codetype$\lbrack\!\lbrack\;$}
  9.   \def\bewn{$\;\rbrack\!\rbrack$\ \endgroup}
  10. %
  11.  \title{Printing factorials: a demonstration of \cnoweb}
  12.  \synopsis{You are reading a program listing that was formatted
  13.   with \par\item{}{\tt \% tex pf.c}\par
  14.   The same program is compiled
  15.   with \par\item{}{\tt \% cc pf.c}\par
  16.   The key to this dual function source file is a \TeX\ macro
  17.   package called \cnoweb\ that treats all comments as `\TeX-text'
  18.   and all else as `verbatim-text.' The C compiler naturally
  19.   does the opposite and interprets only the text outside the comments.
  20.  
  21.   \nweb In this program comments about 
  22.      \cnoweb\ itself look like this.\bewn}
  23.  \section{Introduction}
  24.  
  25.   This program prints factorials of positive integers.
  26.   It uses this definition of $n!$
  27.   $$ n! = \prod_{i=1}^n i$$
  28.  
  29.   {\narrower
  30.   \nweb \"pf.c" begins with a comment which
  31.   is treated as \TeX-text by \cnoweb.
  32.  
  33.   The first comment contains the
  34.    string *<\input cnoweb>*.  This begins the \cnoweb\ listing.
  35.    Included also in this leading comment section is
  36.    *<\title{Printing ...}>*,
  37.    *<\synopsis{You are reading ...}>*,
  38.    and
  39.    *<\section{Introduction}>*.\bewn\par}
  40.  
  41.   The program is invoked with the command
  42.   \item{}\"pf $[$-l$]$ $[$-e$]$ $n$"
  43.  
  44.   where
  45.    \item{\bf -l} prints the factorials of all numbers
  46.      up to and including the limit $n$.
  47.    \item{\bf -e} includes an exponential notation approximation.
  48.    \item{$n$} is the number whose factorial will be printed.
  49.   */
  50.  
  51. #define GOODEXIT 0          /* exit with this if factorial OK */
  52. #define BADEXIT  1          /* exit with this if error */
  53.  
  54. #include <stdio.h>          /* standard io stuff */
  55. #include <math.h>           /* math stuff */
  56. char     *malloc();         /* memory allocator */
  57.  
  58. /* \section{Big-integer routines}
  59.  
  60.   \"pf" would be trivial were it not for the rapid
  61.   growth of $n!$, which is much greater than exponential
  62.   and quickly surpasses even the real number capacity of most machines.
  63.   We therefore define a new data type (\"Int") to hold big integers.
  64.   */
  65.  
  66.   typedef struct Int_ {
  67.      int radix;                /* $2^1 \le \hbox{radix} \le 2^8$ */
  68.      char *digits;             /* the \"Int"'s digits */
  69.      int length;               /* number of digits available */
  70.      int limit;                /* number of digits in use */
  71.   } Int;
  72.   
  73. /* We do not need many operations on \"Int"s to compute factorials:
  74.    only `set' and `multiply'.
  75.   */
  76.  
  77. /* \subsection{\"Set(I,\ i)"}   
  78.   Return \"I" initialized to \"i". */    
  79.     
  80. Set(I,i) 
  81. Int *I; 
  82. int i;  
  83. {   
  84.    int d;   
  85.    I->digits[0] = (i?1:0);
  86.    for (d=1; d<I->length; I->digits[d++]=0); 
  87.    I->limit = 0;   
  88.    if ((i!=0)&&(i!=1)) Product(I,i);
  89.    return (0);
  90. }   
  91.  
  92. /* \subsection{\"Product(I,\ i)"}   
  93.   Return \"I" multiplied by \"i".
  94.   Returns true if the product is OK. */    
  95.     
  96. Product(I,i) 
  97. Int *I; 
  98. int i;  
  99. {   
  100.    int d,n;   
  101.    int l = I->limit+1;
  102.    int r = I->radix;
  103.    int carry = 0;
  104.  
  105.    for (d=0; ((d<l)||(carry!=0)); d++) { 
  106.      if (d>=I->length) return (0);       /* not enough digits */
  107.      n = I->digits[d] * i + carry;
  108.      if ((I->digits[d] = n % r)>0) I->limit = d;
  109.      carry = n / r;
  110.    }
  111.    return (1);
  112. }   
  113.  
  114.  
  115.  
  116. /* \section{\"main()"} Print the factorial of the integer
  117.    found on the command line.
  118.  
  119.    \item{1.} Parse command line arguments.
  120.    \item{2.} Compute number of digits needed and allocate space.
  121.    \item{3.} Calculate the factorial.
  122.    \item{4.} Print the factorial.
  123.  
  124.      \nweb \cnoweb\ breaks pages only before comments.\hfill\break
  125.      You can control pagination with this knowledge.\bewn
  126.  
  127.      The higher the radix the fewer digits needed, but
  128.      we use an internal radix of 10
  129.      to save a lot of division when printing the number. 
  130.      Also, we already have a log$_{10}$ function.
  131.  
  132.    */
  133.  
  134. #define RADIX 10
  135.  
  136. Int nfactorial;      /* place for the factorial */
  137. Int *nf = &nfactorial;
  138.  
  139. /* command line parameters */
  140.  
  141.  int limit_mode = 0;        /* true if printing all factorials */
  142.  int expon_mode = 0;        /* true if printing exponential notation */
  143.  
  144. /* start of the program */
  145.  
  146. main(argc,argv)
  147. int  argc;
  148. char *argv[];
  149. {
  150.  int n;
  151.   int i;
  152.  
  153.   /* 1. Parse the command line */
  154.  
  155.   n = parse_args(argc,argv);  /* we will print $n!$ */
  156.  
  157.   /* 2. Compute digits needed and allocate space */
  158.  
  159.   nf->radix = RADIX;
  160.   nf->length = digits(n,RADIX);
  161.  
  162.   if ((nf->digits = malloc(nf->length))==NULL) {
  163.      printf("Sorry, cannot allocate space for %d digits\n",
  164.          nf->length);
  165.      exit (BADEXIT);
  166.   }
  167.   
  168.   /* 3. Calculate the factorial.  */
  169.  
  170.   Set(nf,1);         /* initialize \"nf" */
  171.  
  172.   for (i=1; i<=n; i++) {
  173.      if (Product(nf,i)==0) {
  174.         printf("Sorry, miscalculated the number of digits.\n");
  175.         exit (BADEXIT);
  176.      }
  177.      if (limit_mode) print_Int(nf,i);
  178.   }
  179.  
  180.   /* 4. Print the result, if it hasn't been printed yet. */
  181.  
  182.   if (!limit_mode) print_Int(nf,n);
  183.   exit (GOODEXIT);
  184. }
  185.  
  186. /* \subsection{\"parse_args(argc,argv)"}
  187.  
  188.      This is a standard UNIX idiom.
  189.      See Kernighan \& Ritchie.
  190.  
  191.     \nweb \cnoweb\ automatically indents after 
  192.       {\tt\char`\{} and {\tt\char`\(}.\bewn */
  193.  
  194. parse_args(argc,argv)
  195. int argc;
  196. char *argv[];
  197. {
  198.   int n = (-1);
  199.  
  200.   while (--argc > 0) {
  201.     argv++;
  202.     if (argv[0][0]=='-') {   /* is an option  flag */
  203.        switch (argv[0][1]) {
  204.           case 'l': {
  205.             limit_mode = 1;
  206.             break;
  207.           }
  208.           case 'e': {
  209.             expon_mode = 1;
  210.             break;
  211.           }
  212.           default: show_usage();
  213.        }
  214.     } else {                 /* is the number */
  215.        sscanf(argv[0],"%d",&n);
  216.     }
  217.   }
  218.  
  219.   if (n<=0) show_usage();
  220.   return (n);
  221. }
  222.  
  223. /* \subsection{\"digits(n,r)"} Returns number of digits in \"n"
  224.    using a radix of \"r".
  225.  
  226.      A factorial can be approximated by the Sterling formula
  227.      $$ n! \approx e^{-n} n^{n} \sqrt{2\pi n}$$
  228.      What we want is the number of digits, which is
  229.      $$ \hbox{\# digits} \approx \log_r(n!)=\log(n!)/\log(r) \approx
  230.         (-n \log e + n \log n + {1\over2}\log (2\pi n))/\log(r)$$
  231.  
  232.      We will add a couple of digits to this value
  233.      to allow for the approximations and assure that we
  234.      have enough.
  235.   */
  236.  
  237. #define PI    3.141592653589793238462643   /* $\pi$ */
  238. #define E     2.718281828459045235360287   /* $e$ */
  239.  
  240. digits(n,r)
  241. int n;
  242. int r;
  243. {
  244.   double dn = n;
  245.   int nd;
  246.  
  247.   nd = (int)((-dn * log10(E)) + 
  248.      (dn * log10(dn)) + (.5 * log10(2*PI*dn)))/log10((double)r) + 2;
  249.   /* *<printf("requires %d digits\n",nd);>* */
  250.  
  251.   /* \nweb The
  252.   `Commented out' code above was typed: 
  253.   {\tt/{}* *{}<printf...;>{}* *{}/}.\bewn */
  254.  
  255.   return (nd);
  256. }
  257.  
  258. /* \subsection{\"print_Int(I,\ i)"}   
  259.   Print {\tt{\it value(}i{\it)} = {\it value(}I{\it)}}.
  260.   The internal radix that matches the display radix
  261.   clearly makes this procedure easier.
  262.  
  263.   This display uses the convention that separates each
  264.    three-digit set with commas.
  265. */    
  266.     
  267. #define MAX_WIDTH 80            /* maximum width of the output */
  268.  
  269. print_Int(I,i) 
  270. Int *I; 
  271. int i;  
  272. {   
  273.    int d;   
  274.    int lp,bp;
  275.    char line[MAX_WIDTH];
  276.  
  277.    sprintf(line,"%d! = ",i);
  278.    bp = lp = strlen(line);
  279.    for (d=I->limit; d>=0; d--) {
  280.       line[lp++] = I->digits[d] + '0';  /* assumes radix $\le 10$ */
  281.       if ((d%3)==0) {
  282.          line[lp++] = (d?',':'.');
  283.          if ((d==0) || (lp>MAX_WIDTH-5)) {
  284.            line[lp] = '\0';
  285.            printf("%s\n",line);
  286.            for (lp=0; lp<bp; line[lp++]=' ');
  287.          }
  288.       }  
  289.    }
  290.  
  291.    /* If the exponential notation was desired, print it now.
  292.       */
  293.  
  294.    if (expon_mode) {
  295.       int d = I->limit;       /* the most significant digit */
  296.       sprintf(line+bp,"approximately = %d.%d x 10e%d",
  297.         I->digits[d],d?I->digits[d-1]:0,d);
  298.       printf("%s\n",line);
  299.    }
  300.    return (0);
  301. }
  302.  
  303. /* \section{\"show_usage()"} invocation syntax error---show 
  304.    correct usage */ 
  305.     
  306. int show_usage()
  307. {   
  308.    printf("usage: pf [-l] [-e] positive_integer\n"); 
  309.    exit (BADEXIT);
  310. }   
  311.  
  312. /* \section{Summary of \cnoweb\ commands}
  313.  
  314.    These control sequences are defined in the \cnoweb\ macro package.
  315.  
  316.    \begingroup
  317.      \def\{{{\tt\char`\{}}
  318.      \def\}{{\tt\char`\}}}
  319.      \def\cs#1{\smallskip\noindent\hangindent7\blockindent\hangafter1
  320.         \hbox to7\blockindent{\bf#1\qquad\hss}\ignorespaces}
  321.  
  322.    \cs{\\title\{ ... \}} Titles the program.
  323.    \cs{\\job\{ ... \}} Another title area. Defaults to input filename.
  324.    \cs{\\section\{ ... \}} Begins a section.  The section title 
  325.     is also included in the table of contents and 
  326.     in the page header.
  327.    \cs{\\subsection\{ ... \}} Begins a subsection.  The subsection title 
  328.     is also included in the table of contents.
  329.    \cs{\\subsubsection\{ ... \}} Begins a subsubsection.  
  330.     The subsubsection title 
  331.     is also included in the table of contents.
  332.    \cs{\\newpage} Causes a page eject after the current line.  This 
  333.     is usually used in a comment by itself, e.g.,
  334.     \hbox{\tt /{}* \\newpage *{}/}.
  335.    \cs{\\endc} Ends the \cnoweb\ listing.  This
  336.     is usually the last line in the file, e.g.,
  337.     \hbox{\tt /{}* \\endc *{}/}.
  338.    \cs{\\{\tt"} ... {\tt"}} Prints {\bf bold} text.
  339.    \cs{\\{\tt'} ... {\tt'}} Prints {\it italic} text.
  340.    \cs{\\{\tt|} ... {\tt|}} Prints {\tt typewriter} text.
  341.    \cs{*{\tt<} ... {\tt>}*} Allows C code to be included in comments.
  342.       You can nest comments within the `commented out' C code, e.g.,
  343.       \hfill\break 
  344.       {\tt/{}* comment out this section *{}<} \hfill\break
  345.       \hglue\blockindent{\tt i = 0; /{}* initialize \"i" *{}/} \hfill\break
  346.       \hglue\blockindent{\tt ...}  \hfill\break
  347.       \hglue\blockindent{\tt >{}* end of the commented out section *{}/}
  348.       
  349.    \cs{\\item, \\hang, {\rm etc.}} Work as you hope they would.
  350.   \endgroup
  351.  
  352.   */
  353.     
  354. /* \section{How to obtain \cnoweb}
  355.  
  356.   You may obtain \cnoweb\ by anonymous ftp to
  357.   {\tt u.washington.edu}.
  358.  
  359.   It is in the directory:  {\tt pub/tex/cnoweb}
  360.  
  361.   \bigskip
  362.     \rightline{--- Jim Fox,
  363.      University of Washington}
  364.     \rightline{\strut \tt fox@cac.washington.edu}
  365.  
  366.    \medskip
  367.  
  368.    The file ends with the comment
  369.     `{\tt /{}* \\endc *{}/}' */
  370.    
  371. /* \endc */ 
  372.